package com.jdaw.datastructure.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr ={8,9,1,7,2,3,5,4,6,0};
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    //交换法进行希尔排序
    public static void shellSort(int[] arr){
        for(int gap=arr.length/2;gap>0;gap/=2){
            for(int i=gap;i<arr.length;i++){
                for(int j=i-gap;j>=0;j-=gap) {
                    if (arr[j] > arr[j + gap]) {
                        int temp;
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    //移位法进行希尔排序
    public static void shellSort2(int[] arr){
        for(int gap=arr.length/2;gap>0;gap/=2){
            //从第gap个元素逐个对其所在的组进行直接插入排序
            for(int i=gap;i<arr.length;i++){
                int j=i;
                int temp=arr[j];
                if(arr[j]<arr[j-gap]){
                    while(j-gap>=0&&temp<arr[j-gap]){
                        //移动
                        arr[j]=arr[j-gap];
                        j-=gap;
                    }
                    //退出while说明找到了位置
                    arr[j]=temp;
                }
            }
        }

    }

}
